package tree;

import common.Person;
import file.Files;
import printer.BinaryTrees;

import java.util.Comparator;

/**
 * @author 陈艺博
 * @date 2021-02-28 20:33
 * @description 搜索二叉树测试类
 **/
public class BinarySearchTreeTest {

    // 创建自定义比较器
    private static class PersonComparator1 implements Comparator<Person> {
        @Override
        public int compare(Person o1, Person o2) {
            return o1.getAge() - o2.getAge();
        }
    }

    private static class PersonComparator2 implements Comparator<Person> {
        @Override
        public int compare(Person o1, Person o2) {
            return o2.getAge() - o1.getAge();
        }
    }

    // 1. 测试添加方法
    static void test1() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 3, 12, 1};

        BinarySearchTree<Object> bst1 = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst1.add(data[i]);
        }
        BinaryTrees.println(bst1);
    }

    // 2. 测试对象比较器
    static void test2() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 3, 12, 1};

        BinarySearchTree<Person> bst2 = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst2.add(new Person(data[i]));
        }
        BinaryTrees.println(bst2);

        BinarySearchTree<Person> bstComparator = new BinarySearchTree<>(new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                // 左大右小
                return o2.getAge() - o1.getAge();
            }
        });
        for (int i = 0; i < data.length; i++) {
            bstComparator.add(new Person(data[i]));
        }
        BinaryTrees.println(bstComparator);
    }

    // 3. 测试树可视化输出到文件中
    static void test3(){
        BinarySearchTree<Integer> bst3 = new BinarySearchTree<>();
        for (int i = 0; i < 40; i++) {
            bst3.add((int)(Math.random()*100));
        }

        BinaryTrees.println(bst3);
        String str = BinaryTrees.printString(bst3);
        str += "\n";
        Files.writeToFile("F:/bstOut.txt",str,true);
        System.out.println("输出成功， 位置"+"F:/bstOut.txt");
    }

    // 4. 测试相同年龄节点覆盖旧值
    static void test4() {
        BinarySearchTree<Person> bst = new BinarySearchTree<>();
        bst.add(new Person(10, "jack"));
        bst.add(new Person(12, "rose"));
        bst.add(new Person(6, "jim"));

        bst.add(new Person(10, "michael"));

        BinaryTrees.println(bst);
    }

    // 5. 测试前序遍历
    static void test5() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Object> bst5 = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst5.add(data[i]);
        }
        bst5.preorderTraversal();
    }

    // 6. 测试中序遍历
    static void test6() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Object> bst5 = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst5.add(data[i]);
        }
        bst5.inorderTraversalDesc();
    }

    // 7. 测试后序遍历
    static void test7() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Object> bst5 = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst5.add(data[i]);
        }
        bst5.postorderTraversal();
    }

    // 8. 测试层次遍历
    static void test8() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Object> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
        bst.levelOrderTraversal();
    }

    // 9. 自定义访问器
    static void test9() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);

        bst.postorder(new BinarySearchTree.Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                System.out.print("_" + element + " ");

                return element == 11 ? true : false;
            }
        });
    }

    // 10. 测试增强遍历停止方法
    static void test10() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);

        bst.preorder(new BinarySearchTree.Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                System.out.print("_" + element + " ");
                return element == 1;
            }
        });

        System.out.println();
        bst.inorder(new BinarySearchTree.Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                System.out.print("_" + element + " ");
                return element == 4;
            }
        });

        System.out.println();
        bst.postorder(new BinarySearchTree.Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                System.out.print("_" + element + " ");
                return element == 5;
            }
        });

        System.out.println();
        bst.levelOrder(new BinarySearchTree.Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                System.out.print("_" + element + " ");
                return element == 2;
            }
        });
    }

    // 11. 获取二叉树的高
    static void test11() {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < 15; i++) {
            bst.add((int) (Math.random() * 100));
        }
        BinaryTrees.println(bst);

        System.out.println("Tree Height: " + bst.height1());
    }

    // 12. 判断是否为完全二叉树
    static void test12() {
        Integer data[] = new Integer[]{7, 4, 9, 2, 1};

        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);

        System.out.println("Is this a CompleteBinaryTree: " + bst.isComplete1());
    }

    // 13. 测试删除功能
    static void test13() {

        Integer data[] = new Integer[]{7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);

        //测试删除部分
        bst.remove(3);
        bst.remove(10);
        BinaryTrees.println(bst);
        bst.remove(2);
        bst.remove(11);
        BinaryTrees.println(bst);
        bst.remove(9);
        BinaryTrees.println(bst);
    }

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
//        test5();
//        test6();
//        test7();
//        test8();
//        test9();
//        test10();
//        test11();
//        test12();
        test13();
    }
}
